public class Test {
    public static void main(String[] args) {
        //
    }
}

class Solution {
    int[] tmp;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    //归并排序（递归）
    private void sort(int[] nums,int l, int r){
        //[l,r]——要归并的数组区间
        if(l >= r) return;//只有一个元素，或者不存在，排序完成


        //感觉这里可能会写出死循环。。。。注意边界
        int mid = l + (r - l)/2;//随机找一个下标，作为分割（这里是中间位置，不是随机）
        //[l,mid] 左区间；[mid+1,r] 右区间
        sort(nums,l,mid);//处理左区间
        sort(nums,mid+1,r);//处理右区间

        //合并两个有序数组
        catArray(nums,l,r,mid);

    }
    //合并两个有序数组（并且，真正的排序逻辑其实在这里体现）
    private void catArray(int[] nums,int l,int r,int mid) {
        //
        int cur1 = l;
        int cur2 = mid+1;
        int i = 0;
        while(cur1 <= mid && cur2 <= r)
           tmp[i++] = (nums[cur1] < nums[cur2]) ? nums[cur1++] : nums[cur2++];
        while(cur1 < mid )//老师这里的处理非常巧妙，不仅能判断是哪个没“走完”，还可以充当循环条件（实际也是这个条件判断是否循环~~~）
            tmp[i++] = nums[cur1++];
        while(cur2 < r )
            tmp[i++] = nums[cur2++];

        //放回去！！！
        /*for(int j = 0; j < r-l+1; j++){
            nums[l++] = tmp[j];
        }*/
        for(int j = l;j<=r;j++){
            nums[j] = tmp[j-l];
        }

    }

}